#define _CRT_SECURE_NO_WARNINGS   1

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

struct Edge {
	int u, v;

	Edge(int u = 0, int v = 0) : v(v), u(u) {}
};

struct Node {
	int x, d;

	Node(int x = 0, int d = 0) : x(x), d(d) {}
	bool operator <(const Node& o) const {
		return d > o.d;
	}
};

int n = 0, m = 0;
int d[5009];
Edge edge[100009];
int first[5009], next1[100009];
bool vis[5009];

void dij(int);

int main() {
	scanf("%d%d", &n, &m);
	memset(first, -1, sizeof(first));
	for (int i = 0; i < m; i++) {
		int a = 0, b = 0, v = 0;
		int t = i << 1;
		scanf("%d%d%d", &a, &b, &v);
		edge[t] = Edge(b, v);
		edge[t | 1] = Edge(a, v);
		next1[t] = first[a];
		first[a] = t;
		next1[t | 1] = first[b];
		first[b] = t | 1;
	}
	dij(1);
	printf("%d\n", d[n]);
	return 0;
}

void dij(int s) {
	memset(d, -1, sizeof(d));
	memset(vis, 0, sizeof(vis));
	d[s] = 0;
	priority_queue<Node> pq;
	pq.push(Node(s, 0));
	while (!pq.empty()) {
		Node u = pq.top(); pq.pop();
		int x = u.x;
		if (vis[x]) continue;
		vis[x] = true;
		for (int i = first[x]; i != -1; i = next1[i]) {
			Edge& e = edge[i];
			if (!vis[e.u] && (d[e.u] == -1 || d[e.u] > d[x] + e.v)) {
				d[e.u] = d[x] + e.v;
				pq.push(Node(e.u, d[e.u]));
			}
		}
	}
}

